import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.LinkedList;


public class OptimizeSudokuResolver {

	private final static int NB_LIGNE_COLONNE = 9;
	
	private LinkedList<LinkedList<Node>> grille = new LinkedList<LinkedList<Node>>();
	private LinkedList<Node> solutions = new LinkedList<Node>();
	
	public OptimizeSudokuResolver()
	{
		for(int x = 0; x < NB_LIGNE_COLONNE; x++)
		{		
			grille.add(new LinkedList<Node>());
		}
	}
	
	public static void main(String[] args) {
		OptimizeSudokuResolver sudRes = new OptimizeSudokuResolver();
		
		sudRes.lireFichier(args[0]);
		
		long time = System.currentTimeMillis();
		
		sudRes.resoudre((ColumnNode)sudRes.grille.get(0).get(0).getUp());
		
		System.out.println("Temps d'exécution : " + (System.currentTimeMillis() - time) + " ms");
		
		//sudRes.afficherGrille();
		sudRes.afficherSolution();
		
	}
	
	//Affiche la grille, utiliser pour les tests
	void afficherGrille()
	{
		ColumnNode h = (ColumnNode)grille.get(0).get(0).getUp().getLeft();
		ColumnNode n = (ColumnNode)h.getRight();
		while (n != h) {
			System.out.print(n.getName());
			n = (ColumnNode)n.getRight();
		}
		
		System.out.println();
		
		for(int y = 0; y < NB_LIGNE_COLONNE; y++)
		{
			for(int x = 0; x < NB_LIGNE_COLONNE; x++)
			{
				System.out.print(grille.get(x).get(y).getChiffre());
			}
			System.out.println();
		}	
	}
	
	//Affiche la solution finale ...
	void afficherSolution()
	{
		for(int cpt = 0; cpt < solutions.size(); cpt++)
		{
			if(cpt % 9 == 0)
				System.out.println();
			
			System.out.print(solutions.get(cpt).getChiffre());
		}
	}

	void lireFichier(final String nomFichier)
	{
		try {
			FileReader fr = new FileReader(nomFichier);
			
			for(int y = 0; y < NB_LIGNE_COLONNE; y++) 
			{
				for(int x = 0; x < NB_LIGNE_COLONNE; x++) 
				{
					Node node = new Node();
					node.setChiffre(Integer.parseInt(new String(String.valueOf((char) fr.read()))));
	
					grille.get(x).add(y, node);
					
					if(x != 0)
					{
						node.setLeft(grille.get(x - 1).get(y));
						grille.get(x - 1).get(y).setRight(node);	
					}
					
					if (y != 0)
					{
						node.setUp(grille.get(x).get(y - 1));
						grille.get(x).get(y - 1).setDown(node);
					}
					
				}
				fr.skip(2); //skip \n\r
			}
			
			fr.close();
			
			for(int i = 0; i < 9; i++)
			{
				ColumnNode node = new ColumnNode((char)(65 + i));	
				
				node.setDown(grille.get(i).get(0));
				node.setUp(grille.get(i).get(8));
				
				grille.get(i).get(0).setUp(node);
				grille.get(i).get(8).setDown(node);
				
				if(i != 0)
				{
					node.setLeft(grille.get(i - 1).get(0).getUp());
					grille.get(i - 1).get(0).getUp().setRight(node);
				}
				
				//Ceci va faire que le : EX:x=0,y=0 pointe et soit pointer sur x=8,y=8
				grille.get(0).get(i).setLeft(grille.get(0).get(8 - i));
				grille.get(0).get(8 - i).setRight(grille.get(0).get(i));
			}
					
			ColumnNode h = new ColumnNode('h');
			
			h.setRight(grille.get(0).get(0).getUp());
			grille.get(0).get(0).getUp().setLeft(h);
			
			h.setLeft(grille.get(8).get(8).getDown());
			grille.get(8).get(8).getDown().setRight(h);
			
			afficherGrille();
			
		} catch (FileNotFoundException e) {
			e.printStackTrace();
		} catch (IOException e) {
			e.printStackTrace();
		}
	}
	
	boolean estValide(final Node node, final int k)
	{
		/*for(int cpt = 0; cpt < NB_LIGNE_COLONNE; cpt++)
		{
			if(grille[x][cpt] == k || grille[cpt][y] == k)
				return false;	
		}
		
		final int limiteX = (x/3) * 3;
		final int limiteY = (y/3) * 3;
		
		for(int cpt = 0; cpt < 3; cpt++)
		{
			final int posX = limiteX + cpt;
			
			if(grille[posX][limiteY] == k)
				return false;
			
			if(grille[posX][limiteY + 1] == k)
				return false;
			
			if(grille[posX][limiteY + 2] == k)
				return false;
		}*/
		
		return true;
	}
	
	ColumnNode chooseNextColumn()
	{
		int size = Integer.MAX_VALUE;
		int pos = 0;
		
		for(int x = 0; x < 9; x++)
		{
			final int columnSize = ((ColumnNode)grille.get(x).get(0).getUp()).size();
			
			if (size > columnSize)
			{
				size = columnSize;
				pos++;
			}
		}

		return (ColumnNode)grille.get(pos).get(0).getUp();
	}
	
	void resoudre(ColumnNode colNode)
	{
		if (colNode.getRight() == colNode)
		{
			afficherGrille();
			return;
		}
		else
		{
			ColumnNode column = chooseNextColumn(); 
	     	cover(column); 

	     	for( Node rowNode = column.getDown() ; rowNode != column ; rowNode = rowNode.getDown() ) { 
	           	solutions.add( rowNode ); 

	           	for( Node rightNode = rowNode.getRight() ; rightNode != rowNode ; rightNode = rightNode.getRight() ) 
	                	cover( (ColumnNode)rightNode ); 

	           	resoudre((ColumnNode)rowNode.getRight().getUp()); 

	            solutions.remove( rowNode ); 
	            column = (ColumnNode)rowNode.getColumn(); 

	          	for( Node leftNode = rowNode.getLeft() ; leftNode != rowNode ; leftNode = leftNode.getLeft() ) 
	               	uncover( (ColumnNode)leftNode ); 
	      } 

	     uncover( column ); 
		}
	}
	
	void cover(ColumnNode colNode)
	{
		Node column = colNode.getColumn(); 

		column.getRight().setLeft( column.getLeft() ); 
		column.getLeft().setRight( column.getRight() ); 

		for( Node row = column.getDown() ; row != column ; row = row.getDown() ) 
		     	for( Node rightNode = row.getRight() ; rightNode != row ; rightNode = rightNode.getRight() ) { 
		          	rightNode.getUp().setDown( rightNode.getDown() ); 
		          	rightNode.getDown().setUp( rightNode.getUp() ); 
		     	} 
	}
	
	void uncover(ColumnNode colNode)
	{
		Node column = colNode.getColumn(); 

		for( Node row = column.getUp() ; row != column ; row = row.getUp() ) 
		     	for( Node leftNode = row.getLeft() ; leftNode != row ; leftNode = leftNode.getRight() ) { 
		          	leftNode.getUp().setDown( leftNode.getDown() ); 
		          	leftNode.getDown().setUp( leftNode.getUp() ); 
		     	} 
		column.getRight().setLeft( column.getLeft() ); 
		column.getLeft().setRight( column.getRight() ); 
	}
}
